package three;
import java.util.*;

public class A045 {



    public void flatten(TreeNode root) {
        //整体往右边遍历，左边不空则进入


        //1.判断当前节点cur左边是否为空，为空就一直往右边走
        //2.左边不为空，将起点暂时定位左边next和prev，然后让一个前驱节点prev一直往右边走
        //3.当走到最右边（或者没有），就开始拼接
        //4.当前序节点的右边接上cur的右边，并且将cur左边置空
        //5.最后将cur的右边给next
        //1.
        TreeNode cur = root;
        while(cur!=null) {
            //2.
            if(cur.left!=null) {
                TreeNode next = cur.left;
                TreeNode prev = next;
                //3.
                while(prev.right!=null) {
                    prev = prev.right; //一直往右
                }
                //4.
                prev.right=cur.right;
                cur.left=null;
                //5.
                cur.right = next;
            }
            //1.
            cur = cur.right;
        }
    }






















    //思路：先“前序遍历”把所有节点放入队列中，再一个个拿出来拼接上

    Queue<TreeNode> queue = new LinkedList<>();
    public void flatten1(TreeNode root) {
        if(root==null) return;
        preorder(root);
        TreeNode prev = queue.poll();
        while(!queue.isEmpty()) {
            prev.left=null;//将左边置空
            TreeNode next = prev;
            if(!queue.isEmpty()) next = queue.poll();
            else break;
            prev.right=next;
            prev=next;
        }
        prev.left=null; //将最后一个节点置空
    }

    public void preorder(TreeNode root) {
        if(root==null) return;
        queue.add(root);
        preorder(root.left);
        preorder(root.right);
    }
}
